package com.lihepeng.leecode.tree;

/**
 *给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
 *
 * 创建一个根节点，其值为 nums 中的最大值。
 * 递归地在最大值 左边 的 子数组前缀上 构建左子树。
 * 递归地在最大值 右边 的 子数组后缀上 构建右子树。
 * 返回 nums 构建的 最大二叉树 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 */
public class Solution654 {
    /**
     * 整理思路
     * 首先遍历数组找到 最大的值
     * 然后将小的值放到当前节点 左边，大的值 放到当前节点的右边
     *
     * @param nums
     * @return
     */
    private TreeNode constructMaximumBinaryTree(int[] nums) {

        return  constructMaximumBinaryTree(nums,0,nums.length);
    }
    private TreeNode constructMaximumBinaryTree(int[]nums,int from,int to){
        if (from==to){
            return null;
        }
        int num  = Integer.MIN_VALUE;
        // 找到 最大值 并且记录最大值的索引 i
        int index =from;
        for (int i=from;i<to;i++) {
            if (nums[i]>num){
                num=nums[i];
                index =i;
            }

        }
        TreeNode treeNode = new TreeNode(num);
        // 递归元素
        treeNode.left = constructMaximumBinaryTree(nums,from,index);
        treeNode.right = constructMaximumBinaryTree(nums,index+1,to);
        return treeNode;
    }
}
